package com.lry.basic.algorithm.graph;

import java.util.ArrayList;
import java.util.List;

public class UndirectedGraphDFS{
    private List<Integer> preOrders = new ArrayList<>();
    private List<Integer> postOrders = new ArrayList<>();
    private UndirectedGraph graph;
    private boolean[] visited;
    public UndirectedGraphDFS(UndirectedGraph graph){
        this.graph = graph;
        visited = new boolean[graph.vertexNum()];
        //可能有多个连通分量，所以得for
        for(int v=0;v<graph.vertexNum();v++){
            if(!visited[v]){
                dfs(v);
            }
        }
    }

    private void dfs(int v){
        visited[v] = true;
        preOrders.add(v);
        for(int w:graph.adj(v)) {
            if(!visited[w]){
                dfs(w);
            }
        }
        postOrders.add(v);
    }


    public Iterable<Integer> getPreOrders(){
        return preOrders;
    }
    public Iterable<Integer> getPostOrders(){
        return postOrders;
    }
    public static void main(String[] args) {
        UndirectedGraph graph = new UndirectedGraph("graph.txt");
        System.out.println(graph);
        UndirectedGraphDFS graphDFS = new UndirectedGraphDFS(graph);
        System.out.println(graphDFS.getPreOrders());
        System.out.println(graphDFS.getPostOrders());
    }
}
